Before starting the main loop of Dijkstra's, we must initialize the necessary data structures for tracking distances and paths.

  • The distances dictionary $d[v]$ is created, mapping every vertex $v$ to a cost.
  • The distance to the source node $s$ is set to $d[s] = 0$.
  • The distance to all other nodes $v \neq s$ is set to infinity ($\infty$), indicating they are unreachable initially.
  • A Priority Queue (PQ) is initialized and populated with the source node and its distance: $(0, s)$.
  • An optional previous node tracker is initialized to `None` for all nodes, used later to reconstruct the shortest path.
Python: Dijkstra Initialization
1# Assume G is our weighted_graph, start_node = 'A'
2distances = {node: float('inf') for node in G}
3distances[start_node] = 0
4
5# Priority queue stores (distance, node)
6pq = [(0, start_node)] 
7
8previous = {node: None for node in G}